Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Medium

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree.

Accepted

305,239

Submissions

598,646

Seen this question in a real interview before?

Companies

Solution

How to traverse the tree

There are two general strategies to traverse a tree:

Depth First Search (DFS)

In this strategy, we adopt the depth as the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.

The DFS strategy can further be distinguished as preorder, inorder, and postorder depending on the relative order among the root node, left node and right node.
Breadth First Search (BFS)

We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

On the following figure the nodes are enumerated in the order you visit them, please follow 1-2-3-4-5 to compare different strategies.

postorder

In this problem one deals with inorder and postorder traversals.

Approach 1: Recursion

How to construct the tree from two traversals: inorder and preorder/postorder/etc

Problems like this one are often at Facebook interviews, and could be solved in $\mathcal{O}(N)$ time:

Start from not inorder traversal, usually it's preorder or postorder one, and use the traversal picture above to define the strategy to pick the nodes. For example, for preorder traversal the first value is a root, then its left child, then its right child, etc. For postorder traversal the last value is a root, then its right child, then its left child, etc.
The value picked from preorder/postorder traversal splits the inorder traversal into left and right subtrees. The only information one needs from inorder - if the current subtree is empty (= return None) or not (= continue to construct the subtree).

bla

Algorithm

Build hashmap value -> its index for inorder traversal.
Return helper function which takes as the arguments the left and right boundaries for the current subtree in the inorder traversal. These boundaries are used only to check if the subtree is empty or not. Here is how it works helper(in_left = 0, in_right = n - 1):
- If in_left > in_right, the subtree is empty, return None.
- Pick the last element in postorder traversal as a root.
- Root value has index index in the inorder traversal, elements from in_left to index - 1 belong to the left subtree, and elements from index + 1 to in_right belong to the right subtree.
- Following the postorder logic, proceed recursively first to construct the right subtree helper(index + 1, in_right) and then to construct the left subtree helper(in_left, index - 1).
- Return root.

Implementation

1 / 7

Complexity Analysis

Time complexity : $\mathcal{O}(N)$ . Let's compute the solution with the help of master theorem $T(N) = aT\left(\frac{b}{N}\right) + \Theta(N^d)$ . The equation represents dividing the problem up into $a$ subproblems of size $\frac{N}{b}$ in $\Theta(N^d)$ time. Here one divides the problem in two subproblemes a = 2, the size of each subproblem (to compute left and right subtree) is a half of initial problem b = 2, and all this happens in a constant time d = 0. That means that $\log_b(a) > d$ and hence we're dealing with case 1 that means $\mathcal{O}(N^{\log_b(a)}) = \mathcal{O}(N)$ time complexity.
Space complexity : $\mathcal{O}(N)$ , since we store the entire tree.

Report Article Issue

Comments: 20

BestMost VotesNewest to OldestOldest to Newest

SoumavaBan100

September 2, 2019 2:22 AM

What is the reason that we have to construct the right sub-tree first and then the left sub-tree?

Show 9 replies

Report

cxhcxh105

November 12, 2020 5:51 PM

[Java] Recursive | Easy to understand

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0 || postorder.length == 0) return null;
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        if(postorder.length == 1) return root;

        int index = 0;
        for(int val : inorder){
            if(val == root.val) break;
            index++;
        }

        root.left = buildTree(Arrays.copyOfRange(inorder, 0, index), Arrays.copyOfRange(postorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(inorder, index + 1, inorder.length), Arrays.copyOfRange(postorder, index, postorder.length - 1));

        return root;
    }

Show 3 replies

Report

lenchen11122845

Last Edit: February 2, 2020 6:16 PM

Refer to the greate answer of @StefanPochmann in this post.
It's possible to reach O(N) time without the index map.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def build(bound = None):
            if not inorder or inorder[-1] == bound: return None
            root = TreeNode(postorder.pop())
            root.right = build(root.val)
            inorder.pop()
            root.left = build(bound)
            return root

        return build()

Show 3 replies

Report

FCookie110

January 24, 2020 1:10 AM

Since we are popping nodes from the end from post-order list, we come across nodes in the order: node, node.right and then node.left

Report

LeanderLXZ7

November 10, 2020 1:14 PM

A very simple Python implementation.

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
    if not inorder:
        return None
    cur_val = postorder.pop()
    idx = inorder.index(cur_val)
    right = self.buildTree(inorder[idx+1:], postorder)
    left = self.buildTree(inorder[:idx], postorder)
    return TreeNode(cur_val, left, right)

Show 1 reply

Report

antolenin5

April 2, 2020 4:09 PM

My js solution

var splitArray = (arr, splitter) => {
    const index = arr.indexOf(splitter);
    const left = arr.slice(0, index);
    const right = arr.slice(index + 1);
    
    return { left, right };
}

var buildTree = function(inorder, postorder) {
    if (!inorder.length) {
        return null;
    }
    
    const current = postorder.pop();
    const isLeaf = inorder.length === 1;
    
    if (isLeaf) {
        return {
            val: current,
            left: null,
            right: null,
        }
    }
    
    const splitted = splitArray(inorder, current);
    
    return {
        val: current,
        right: buildTree(splitted.right, postorder),
        left: buildTree(splitted.left, postorder),
    }
};

Show 1 reply

Report

drbn4

August 25, 2020 9:18 AM

var buildTree = function(inorder, postorder) {
    if (inorder.length === 0) return null;
    if (inorder.length === 1) return new TreeNode(inorder[0]);

    const rootVal = postorder.pop();
    const leftInOrder = inorder.slice(0, inorder.indexOf(rootVal));
    const rightInOrder = inorder.slice(inorder.indexOf(rootVal)+1, inorder.length);
    
    const leftPostOrder = postorder.slice(0, leftInOrder.length);
    const rightPostOrder = postorder.slice(leftInOrder.length, postorder.length);

    const leftTreeNode = buildTree(leftInOrder, leftPostOrder);
    const rightTreeNode = buildTree(rightInOrder, rightPostOrder);
    
    return new TreeNode(rootVal, leftTreeNode, rightTreeNode);
};

Report

danloringess2

July 8, 2020 1:46 PM

Why is the size of each subproblem half the size of the initial problem? If you have a very unbalanced graph you can have two subproblems one of size 999999 (N-1) and the other with size 1, in that case isn't b very close to 1 and not 2?

Show 1 reply

Report

constantinpojoga0

September 19, 2020 10:25 AM

JS recursive solution:

var buildTree = function(inorder, postorder) {
  if (!postorder.length) return null;
    
  if (postorder.length === 1) {
    return new TreeNode(postorder[0])
  } else {
    const val = postorder.pop();
    const idx = inorder.indexOf(val);
    
    return new TreeNode(
      val, 
      buildTree(inorder.slice(0, idx), postorder.slice(0, idx)),    
      buildTree(inorder.slice(idx + 1), postorder.slice(idx)),
    )
  }
};

Report

Mo_Kiani5

Last Edit: August 16, 2020 12:05 PM

I've managed to solve the problem with iteration and a stack. I've been trying really hard to prove why this solution works, but I'm having trouble solidly articulating it. If anyone knows how to put into words why this solution works I'd really appreciate the help.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not postorder:
            return None
        postIter = reversed(postorder)
        root = TreeNode(next(postIter))
        parentStack = [root]
        
        i = len(inorder) - 1
        for val in postIter:
            node = TreeNode(val)
            if inorder[i] == parentStack[-1].val:
                i -= 1
                parent = parentStack.pop()
                
                while parentStack and inorder[i] == parentStack[-1].val:
                    parent = parentStack.pop()
                    i -= 1
                
                parent.left = node
                parentStack.append(node)
                
            else:    
                parentStack[-1].right = node
                parentStack.append(node)

        return root

Report

Success

Details

Runtime: 16 ms, faster than 79.85% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.

Memory Usage: 26.6 MB, less than 16.12% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.

Next challenges:

Maximum Average Subarray I Add to Array-Form of Integer Maximum Product of Splitted Binary Tree

Show off your acceptance:

Time Submitted	Status	Runtime	Memory	Language
06/17/2021 08:30	Accepted	16 ms	26.6 MB	cpp
05/18/2021 19:19	Accepted	28 ms	26 MB	cpp
05/18/2021 19:14	Accepted	24 ms	26 MB	cpp
07/27/2020 12:43	Accepted	8 ms	23.9 MB	cpp

/23

idx++;
x
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->inorder = inorder;
        this->postorder = postorder;
        postIndex = postorder.size() - 1;
        
        // build hashmap (value -> inorder index)
        int idx = 0;
        for(int val : inorder)
        {
            mp[val] = idx;
            idx++;
        }
        
        return helper(0, inorder.size()-1);
    }
    
private:
    int postIndex;
    vector<int> postorder;
    vector<int> inorder;
    unordered_map<int,int> mp;  // value -> inorder idx
    
    TreeNode* helper(int inLeft, int inRight)
    {
        // No element to construct subtrees
        if(inLeft > inRight)
            return NULL;
        
        // post index element will be the root
        int rootVal = postorder[postIndex];
        TreeNode* root = new TreeNode(rootVal);
        
        // the root splits inorder list into left and right subtree
        int index = mp[rootVal];
        
        postIndex--;
        
        // build the right and left tree recursively
        root->right = helper(index+1, inRight);
        root->left = helper(inLeft, index-1);
        
        return root;
    }
};

Contribute

Type here...(Markdown is enabled)

Saved